package com.dmall.sort.algorithm;

import java.util.Random;

/**
 * 添加随机化的快速排序算法
 * 此算法可以避免数组本身是升序或者降序退化为O(n^2)的算法
 * 但是如果数组的所有元素都一样，那么该算法将退化为O(n^2)的算法
 * @author xiao1.wang
 * @date 2021/10/7 21:32
 */
@SuppressWarnings("all")
public class RandomQuickSort implements Sort {

    private static final Random RANDOM = new Random();

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int random = RANDOM.nextInt(r - l + 1) + l;
        swap(arr, random, r);
        int partition = partition(arr, l, r);
        quickSort(arr, l, partition - 1);
        quickSort(arr, partition + 1, r);
    }

    private int partition(int[] arr, int l, int r) {
        int pivot = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < arr[l]) {
                swap(arr, i, ++pivot);
            }
        }
        swap(arr, l, pivot);
        return pivot;
    }

    @Override
    public String getName() {
        return "随机化的快速排序";
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 4, 7, 2, 8, 3, 1, 10, 5};
        Sort.printArr(arr);
        Sort sort = new RandomQuickSort();
        sort.sort(arr);
        Sort.printArr(arr);
    }
}
